package code1.dp;

/**
 * 原题链接：https://leetcode.cn/problems/coin-change-ii/
 */
public class P518 {

    //零钱兑换，完全背包问题(商品的数量是无限的)
    public int change(int amount, int[] coins) {
        int[] dp=new int[amount+1];             //dp[j]表示凑成总金额为j共有多少种凑法
        dp[0]=1;                                //初始化
        for(int i=0;i<coins.length;i++){        //求组合，先遍历物品再遍历背包容量
            for(int j=coins[i];j<=amount;j++){      //完全背包顺着遍历容量，商品可重复添加
                dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}
